package project.euler.honk.problem.to100;

public final class Problem58 {

	private static boolean isPrime(int number) {
		if (number == 1)
			return false;
		int max = (int) Math.sqrt(number);
		for (int i = 3; i <= max; i+=2) //ignore 2 since no value on the diagonals is even
			if (number % i == 0)
				return false;
		return true;
	}

	public static int solve() {

		int prime = 8;
		int total = 13;
		int n = 4;
		do {
			n++;
			int diff = 2 * n - 2;
			int r_h = 4 * n * n - 10 * n + 7;
			int l_h = r_h + diff;
			int r_l = r_h + 2 * diff;
			int l_l = r_l + diff;

			if (isPrime(r_h)) {prime++;}
			if (isPrime(l_h)) {prime++;}
			if (isPrime(r_l)) {prime++;}
			if (isPrime(l_l)) {prime++;}
			total += 4;
		} while (10 * prime / total >= 1);

		return 2 * n - 1;
	}

	public static void main(String[] args) {
		long start = System.currentTimeMillis();
		int count = solve();
		long end = System.currentTimeMillis();
		System.out.println("Result: " + count + " Time: " + (end - start));
	}

}
